package com.dmall.graph.floodfill;

import java.util.LinkedList;
import java.util.Queue;

public class Leetcode785BFS {
    public boolean isBipartite(int[][] graph) {
        boolean[] visited;
        int[] colors;
        visited = new boolean[graph.length];
        colors = new int[graph.length];

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < graph.length; i++) {
            if (!visited[i]) {
                queue.add(i);
                visited[i] = true;
                colors[i] = 0;
                while (!queue.isEmpty()) {
                    Integer v = queue.remove();
                    for (int w : graph[v]) {
                        if (!visited[w]) {
                            queue.add(w);
                            visited[w] = true;
                            colors[w] = 1 - colors[v];
                        } else if (colors[w] == colors[v]) {
                            return false;
                        }
                    }
                }
            }
        }

        return true;
    }
}
